from collections import defaultdict, deque


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(s) == 0 or len(t) == 0:
            return ''

        target = defaultdict(int)
        for c in t:
            target[c] += 1

        l, r = 0, len(s)

        q = deque()
        stats = {k: 0 for k in target}
        for i, c in enumerate(s):
            if c not in target:
                continue

            q.append([i, c])
            stats[c] += 1

            while len(q) > 1 and stats[q[0][1]] - 1 >= target[q[0][1]]:
                stats[q[0][1]] -= 1
                q.popleft()

            if q[-1][0] - q[0][0] < r - l and all(stats[k] >= target[k] for k in stats):
                l, r = q[0][0], q[-1][0]

        if r == len(s):
            return ''
        return s[l: r+1]


def brutal_solve(s, t):
    if len(s) == 0 or len(t) == 0:
        return ''

    target = defaultdict(int)
    for c in t:
        target[c] += 1

    result = None

    for i in range(len(s)):
        for j in range(i, len(s)):
            if all(s[i: j+1].count(c) >= target[c] for c in target):
                if result is None or j-i < result[1] - result[0]:
                    result = [i, j]
    if result is None:
        return ''

    return s[result[0]: result[1]+1]

# res1 = Solution().minWindow('fgdfd', 'df')
# print(res1)

def test():
    import random
    for i in range(10):
        alphas = 'abcde'

        len_s = random.randint(0, 10)
        s = ''.join(random.choices(alphas, k=len_s))

        len_t = random.randint(0, 10)
        t = ''.join(random.choices(alphas, k=len_t))

        res1 = Solution().minWindow(s, t)
        res2 = brutal_solve(s, t)
        if res1 != res2:
            print(s, t, res1, res2)
test()